#include <iostream>
#include <vector>
#include <map>
#include <math.h>
#include <algorithm>
using namespace std;





















// // 快速排�?785,未通过
// void quick_sort(int q[], int l, int r)
// {
//     int x=(l+r)/2;
//     swap(q[x],q[l]);
//     int tem=q[l];
//     int i=l+1;int j=r;
//     while(i<j){
//         while(q[j]>=tem&&i<j){
//             j--;
//         }
//         while(q[i]<tem&&i<j){
//             i++;
//         }
//         if(i!=j){
//             swap(q[i],q[j]);
//         }
//     }
//     if(q[l]>q[i]){
//         q[l]=q[i];
//         q[i]=tem;
//     }
//     else{
//         i=l;
//     }
//     if(l<i-1){
//         quick_sort(q,l,i-1);
//     }
//     if(r>i+1){
//         quick_sort(q,i+1,r);
//     }
// }
// // 归并排序,accept
// void merge_sort(int a[],int low,int high){
//     if(high==low) return;
//     int mid=(low+high)/2;
//     merge_sort(a,low,mid);
//     merge_sort(a,mid+1,high);
//     int b[high-low+1];
//     int i=low;int j=mid+1;
//     int k=0;
//     bool flag=false;
//     while(i<=mid&&j<=high){
//         if(a[i]<=a[j]){
//             b[k]=a[i];
//             i++;
//             k++;
//             if(i>mid){
//                 flag=true;
//             }
//         }
//         else{
//             b[k]=a[j];
//             j++;
//             k++;
//         }
//     }
//     if(flag){
//         for(;j<=high;j++,k++){
//             b[k]=a[j];
//         }
//     }
//     else{
//         for(;i<=mid;i++,k++){
//             b[k]=a[i];
//         }
//     }
//     for(int x=low,y=0;x<=high;x++,y++){
//         a[x]=b[y];
//     }
// }
// int main(){
//     int n;
//     scanf("%d",&n);
//     int a[n];
//     for(int i=0;i<n;i++){
//        scanf("%d",&a[i]);
//     }
//     merge_sort(a,0,n-1);
//     for(int i=0;i<n;i++){
//         printf("%d ",a[i]);
//     }
// }
// //二分查找 789
// void binary_search(int a[],int low,int high,int num){
//     if(a[high]==num&&a[low]==num){
//         cout<<low<<" "<<high<<endl;
//     }
//     if(a[high]<num||a[low]>num){
//         cout<<"-1 -1"<<endl;
//         return;
//     }
//     int x=(low+high)/2;
//     if(a[x]>num){
//         return binary_search(a,low,x-1,num);
//     }
//     else if(a[x]==num){
//         int i=x;
//         int j=x;
//         while(a[i]==num){
//             i--;
//         }
//         while(a[j]==num){
//             j++;
//         }
//         cout<<i+1<<" "<<j-1<<endl;
//         return;
//     }
//     else {
//         return binary_search(a,x+1,high,num);
//     }
// }
// int main(){
//     int length;
//     int n;
//     scanf("%d %d",&length,&n);
//     int a[length];
//     for(int i=0;i<length;i++){
//         scanf("%d",&a[i]);
//     }
//     for(int i=0;i<n;i++){
//         int num;
//         scanf("%d",&num);
//         binary_search(a,0,length-1,num);
//     }
// }
// 二分法求数的三次方根
// const double jingdu=1e-7;
// void binary_three(double low,double high,double a){
//     double mid=(high+low)/2;
//    if(high-low<jingdu){
//        printf("%lf",mid);
//        return;
//    }
//    if(pow(mid,3)>a){
//        binary_three(low,mid,a);
//    }
//    else{
//        binary_three(mid,high,a);
//    }





// }
// int main(){
//     double a;
//     scanf("%lf",&a);
//     if(a>1){
//     binary_three(jingdu,a,a);

























//     }
//     else if(a<-1){
//         binary_three(a,jingdu,a);
//     }
//     else{
//         binary_three(-1.0,1.0,a);
//     }
// }
// 大数加法 791
// int main(){
//    string s1;
//    string s2;
//    cin>>s1;cin>>s2;
//    int i=s1.length()-1;
//    int j=s2.length()-1;
//    vector<char> tem;
//    int flag=0;
//    while(i>=0&&j>=0){
//        int a=s1[i]-'0'+s2[j]-'0'+flag;
//        flag=0;
//        if(a>=10){
//            a=a-10;
//            flag=1;
//        }
//        i--;
//        j--;
//        tem.push_back(a+'0');
//        cout<<tem[0]<<endl;
//    }
//    while(i>=0){
//        int a=s1[i]-'0'+flag;
//        flag=0;
//         if(a>=10){
//            a=a-10;
//            flag=1;
//        }
//        i--;
//        tem.push_back(a+'0');
//    }
//     while(j>=0){
//        int a=s2[j]-'0'+flag;
//        flag=0;
//         if(a>=10){
//            a=a-10;
//            flag=1;
//        }
//        j--;
//        tem.push_back(a+'0');
//    }
//    if(flag==1){
//        tem.push_back('1');
//    }
//   for(int i=tem.size()-1;i>=0;i--){
//       cout<<tem[i];
//   }
// }
// 大数减法
// void Big_minus(string s1,string s2){
//     int flag=0;
//     vector<char> tem;
//     int i=s1.length()-1;int j=s2.length()-1;
//     while(i>=0&&j>=0){
//         int a=s1[i]-s2[j]-flag;
//         flag=0;
//         if(a<0){
//             flag=1;
//             a=a+10;
//         }
//         i--;
//         j--;
//         tem.push_back(a+'0');
//     }
//     while(i>=0){
//         int a=s1[i]-flag-'0';
//         flag=0;
//          if(a<0){
//             flag=1;
//             a=10+a;
//         }
//         i--;
//         tem.push_back(a+'0');
//     }
//     int k=tem.size()-1;
//     while(tem[k]=='0'){
//         tem.pop_back();
//         k--;
//     }
//     for(int i=tem.size()-1;i>=0;i--){
//           cout<<tem[i];
//      }
// }
// int main(){
//     string s1;
//     string s2;
//     cin>>s1;cin>>s2;
//      if(s1==s2) {
//         cout<<0;
//         return 0;
//     }
//     bool isfu;
//     if(s1.length()<s2.length()) {
//         swap(s1,s2);
//         isfu=true;
//     }
//     if(s1.length()==s2.length()){
//         int i=0;
//        while(i<s1.length()){
//         if(s1[i]==s2[i]){
//             i++;
//         }
//         else if(s1[i]<s2[i]){
//             swap(s1,s2);
//             isfu=true;
//             i=s1.length();
//         }
//         else{
//             i=s1.length();
//         }
//        }
//     }
//     if(isfu){
//         cout<<"-";
//     }
//     Big_minus(s1,s2);
// }
// 动态规划：前缀和：795
// int main(){
//     int n,m;
//     scanf("%d",&n);
//     scanf("%d",&m);
//     int a[n];
//     int i;int j;
//     for(int k=0;k<n;k++){
//         scanf("%d",&a[k]);
//     }
//     int dp[n+1];
//     dp[0]=0;
//     for(int k=1;k<=n;k++){
//         dp[k]=a[k-1]+dp[k-1];
//     }
//     for(int k=0;k<m;k++){
//         scanf("%d",&i);
//         scanf("%d",&j);
//         printf("%d\n",dp[j]-dp[i-1]);
//     }
// }
// 二维动态规划?
//int main(){
//    int n,m,k;
//    cin>>n>>m>>k;
//    int a[n][m];
//    for(int i=0;i<n;i++){
//        for(int j=0;j<m;j++){
//            cin>>a[i][j];
//        }
//    }
//    int dp[n+1][m+1];
//    for(int i=0;i<n+1;i++){
//        for(int j=0;j<m+1;j++){
//            if(i==0||j==0){
//                dp[i][j]=0;
//            }
//            else dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+a[i-1][j-1];
//        }
//    }
//
//    int x1,y1,x2,y2;
//    for(int i=0;i<k;i++){
//        cin>>x1>>y1>>x2>>y2;
//        printf("%d\n",dp[x1-1][y1-1]+dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]);
//    }
//}
// 差分：797
// int main() {
// 	int n, m;
// 	cin >> n >> m;
// 	int a[n];
// 	for (int i = 0; i < n; i++) {
// 		cin >> a[i];
// 	}
// 	int dp[n + 1];
// 	dp[0] = 0;
// 	dp[n] = 0;
// 	for (int i = 1; i < n; i++) {
// 		dp[i] = a[i] - a[i - 1];
// 	}
// 	for (int k = 0; k < m; k++) {
// 		int i, j;
// 		int tem;
// 		cin >> i >> j >> tem;
// 		dp[i - 1] += tem;
// 		dp[j] -= tem;
// 	}
// 	a[0] = dp[0] + a[0];
// 	cout << a[0] << " ";
// 	for (int i = 1; i < n; i++) {
// 		a[i] = a[i - 1] + dp[i];
// 		cout << a[i] << " ";
// 	}
// }